package btree;

import java.io.DataOutputStream;
import java.io.FileOutputStream;
import java.io.IOException;




import exceptions.IndexInsertRecException;
import exceptions.IndexSearchException;
import exceptions.IteratorException;
import exceptions.KeyNotMatchException;
import exceptions.KeyTooLongException;
import exceptions.LeafInsertRecException;

import exceptions.UnpinPageException;

import exceptions.*;
import diskmgr.DiskMgrException;
import diskmgr.DuplicateEntryException;
import diskmgr.FileIOException;
import diskmgr.FileNameTooLongException;
import diskmgr.InvalidPageNumberException;
import diskmgr.InvalidRunSizeException;
import diskmgr.OutOfSpaceException;
import diskmgr.Page;
import exceptions.PinPageException;
import global.AttrType;
import global.GlobalConst;
import global.PageId;
import global.RID;
import global.SystemDefs;
import heap.HFPage;

public class BTreeFile extends IndexFile implements GlobalConst {

	public  BTreeHeaderPage headerPage;
//	private PageId root;
private  PageId headerPageId;
private static FileOutputStream fos;
public static DataOutputStream trace;
public final static String lineSep = System.getProperty("line.separator"); 
public BTreeFile(String fileName) throws ConstructPageException,
			FileIOException, InvalidPageNumberException, DiskMgrException,
			IOException {
	

		PageId pid = SystemDefs.JavabaseDB.get_file_entry(fileName);
		headerPage = new BTreeHeaderPage(pid);
		headerPageId=pid;
		headerPage.setFileName(fileName);
	//	root = headerPage.getRoot();

	}

	public BTreeFile(String filename, int keytype, int keysize,
			int delete_fashion) throws ConstructPageException {

		try {
			headerPageId = SystemDefs.JavabaseDB.get_file_entry(filename);
		} catch (FileIOException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		} catch (InvalidPageNumberException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		} catch (DiskMgrException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		} catch (IOException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
		if (headerPageId == null) // file not exist
		{
			headerPage = new BTreeHeaderPage();
			try {
				headerPageId = headerPage.getCurPage();
			} catch (IOException e) {
				// TODO Auto-generated catch block
				e.printStackTrace();
			}
			try {
				SystemDefs.JavabaseDB.add_file_entry(filename, headerPageId);
			} catch (FileNameTooLongException e) {
				// TODO Auto-generated catch block
				e.printStackTrace();
			} catch (InvalidPageNumberException e) {
				// TODO Auto-generated catch block
				e.printStackTrace();
			} catch (InvalidRunSizeException e) {
				// TODO Auto-generated catch block
				e.printStackTrace();
			} catch (DuplicateEntryException e) {
				// TODO Auto-generated catch block
				e.printStackTrace();
			} catch (OutOfSpaceException e) {
				// TODO Auto-generated catch block
				e.printStackTrace();
			} catch (FileIOException e) {
				// TODO Auto-generated catch block
				e.printStackTrace();
			} catch (DiskMgrException e) {
				// TODO Auto-generated catch block
				e.printStackTrace();
			} catch (IOException e) {
				// TODO Auto-generated catch block
				e.printStackTrace();
			}
//			headerPage.set_magic0(MAGIC0);
			headerPage.setRoot(new PageId(INVALID_PAGE));
			headerPage.setKeyType((short) keytype);
			headerPage.setKeySize(keysize);
			headerPage.setFileName(filename);
			try {
				headerPage.setType(NodeType.BTHEAD);
			} catch (IOException e) {
				// TODO Auto-generated catch block
				e.printStackTrace();
			}
		} else {
			headerPage = new BTreeHeaderPage(headerPageId);
		}

		// try {
		//
		//
		// } catch (IOException e) {
		// // TODO Auto-generated catch block
		// e.printStackTrace();
		// }

	}
	public  BTreeHeaderPage getHeaderPage() {
		return headerPage;
	}

	public  void setHeaderPage(BTreeHeaderPage headerPage) {
		this.headerPage = headerPage;
	}
	public static void traceFilename(String filename) throws IOException {

		fos = new FileOutputStream(filename);
		trace = new DataOutputStream(fos);
	}
	@Override
	public boolean Delete(KeyClass key, RID rid) throws btree.KeyNotMatchException {
		try {
			return NaiveDelete(key, rid);
		} catch (LeafDeleteException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		} catch (KeyNotMatchException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		} catch (PinPageException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		} catch (ConstructPageException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		} catch (UnpinPageException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		} catch (IndexSearchException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		} catch (IteratorException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		} catch (IOException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
		return false;
	}


	private void updateHeader(PageId newRoot) throws IOException,
			PinPageException, UnpinPageException {

		BTreeHeaderPage header;

		header = new BTreeHeaderPage(pinPage(headerPageId));

		headerPage.getRoot();
		header.setRoot(newRoot);

		// clock in dirty bit to bm so our dtor needn't have to worry about it
		unpinPage(headerPageId);

	

	}

	@Override
	public void insert(KeyClass data, RID rid) throws btree.KeyNotMatchException, KeyTooLongException, IOException, KeyNotMatchException {
		// TODO Auto-generated method stub
		if (BT.getKeyLength(data) > headerPage.getKeySize())
		//	throw new KeyTooLongException(null, "");
		if (data instanceof StringKey) {
			if (headerPage.getKeyType() != AttrType.attrString) {
				throw new KeyNotMatchException(null, "");
			}
		} else if (data instanceof IntegerKey) {
			if (headerPage.getKeyType() != AttrType.attrInteger) {
				throw new KeyNotMatchException(null, "");
			}
		} else
			throw new KeyNotMatchException(null, "");
		if (trace != null) {
			try {
				trace.writeBytes("INSERT " + rid.pageNo + " " + rid.slotNo + " "
						+ data + lineSep);
			} catch (IOException e) {
				// TODO Auto-generated catch block
				e.printStackTrace();
			}
			try {
				trace.writeBytes("DO" + lineSep);
			} catch (IOException e) {
				// TODO Auto-generated catch block
				e.printStackTrace();
			}
			try {
				trace.flush();
			} catch (IOException e) {
				// TODO Auto-generated catch block
				e.printStackTrace();
			}
		}
		if (headerPage.getRoot().pid == INVALID_PAGE) {
			PageId newRootPageId = null;
			BTLeafPage newRootPage = null;
			

			try {
				newRootPage = new BTLeafPage(headerPage.getKeyType());
			} catch (ConstructPageException e) {
				// TODO Auto-generated catch block
				e.printStackTrace();
			} catch (IOException e) {
				// TODO Auto-generated catch block
				e.printStackTrace();
			}
			try {
				newRootPageId = newRootPage.getCurPage();
			} catch (IOException e) {
				// TODO Auto-generated catch block
				e.printStackTrace();
			}
			if (trace != null) {
				try {
					trace.writeBytes("NEWROOT " + newRootPageId + lineSep);
				} catch (IOException e) {
					// TODO Auto-generated catch block
					e.printStackTrace();
				}
				try {
					trace.flush();
				} catch (IOException e) {
					// TODO Auto-generated catch block
					e.printStackTrace();
				}
			}
			try {
				newRootPage.setNextPage(new PageId(INVALID_PAGE));
			} catch (IOException e) {
				// TODO Auto-generated catch block
				e.printStackTrace();
			}
			try {
				newRootPage.setPrevPage(new PageId(INVALID_PAGE));
			} catch (IOException e) {
				// TODO Auto-generated catch block
				e.printStackTrace();
			}

			// ASSERTIONS:
			// - newRootPage, newRootPageId valid and pinned

			try {
				newRootPage.insertRecord(data, rid);
			} catch (LeafInsertRecException e) {
				// TODO Auto-generated catch block
				e.printStackTrace();
			}
			if (trace != null) {
				try {
					trace.writeBytes("PUTIN node " + newRootPageId + lineSep);
				} catch (IOException e) {
					// TODO Auto-generated catch block
					e.printStackTrace();
				}
				try {
					trace.flush();
				} catch (IOException e) {
					// TODO Auto-generated catch block
					e.printStackTrace();
				}
			}
			try {
				unpinPage(newRootPageId);
			} catch (UnpinPageException e) {
				// TODO Auto-generated catch block
				e.printStackTrace();
			} 
			 try {
				updateHeader(newRootPageId);
			} catch (PinPageException e) {
				// TODO Auto-generated catch block
				e.printStackTrace();
			} catch (UnpinPageException e) {
				// TODO Auto-generated catch block
				e.printStackTrace();
			} catch (IOException e) {
				// TODO Auto-generated catch block
				e.printStackTrace();
			}
			if (trace != null) {
				try {
					trace.writeBytes("DONE" + lineSep);
				} catch (IOException e) {
					// TODO Auto-generated catch block
					e.printStackTrace();
				}
				try {
					trace.flush();
				} catch (IOException e) {
					// TODO Auto-generated catch block
					e.printStackTrace();
				}
			}
			return;
		}
			if (trace != null) {
				try {
					trace.writeBytes("SEARCH" + lineSep);
				} catch (IOException e) {
					// TODO Auto-generated catch block
					e.printStackTrace();
				}
				try {
					trace.flush();
				} catch (IOException e) {
					// TODO Auto-generated catch block
					e.printStackTrace();
				}
			}
			KeyDataEntry rootEntry = null;
			try {
				try {
					rootEntry = insertP(headerPage.getRoot(), data, rid);
				} catch (NodeNotMatchException e) {
					// TODO Auto-generated catch block
					e.printStackTrace();
				} catch (LeafInsertRecException e) {
					// TODO Auto-generated catch block
					e.printStackTrace();
				} catch (UnpinPageException e) {
					// TODO Auto-generated catch block
					e.printStackTrace();
				} catch (ConstructPageException e) {
					// TODO Auto-generated catch block
					e.printStackTrace();
				}
			} catch (IteratorException e1) {
				// TODO Auto-generated catch block
				e1.printStackTrace();
			} catch (DeleteRecException e1) {
				// TODO Auto-generated catch block
				e1.printStackTrace();
			} catch (ConvertException e1) {
				// TODO Auto-generated catch block
				e1.printStackTrace();
			}
			if (rootEntry != null) {
				// the root is splitted
				// we need new root
				PageId newRootPageId;
				try {
					BTIndexPage newRoot = new BTIndexPage(
							headerPage.getKeyType());
					newRootPageId= newRoot.getCurPage();
					if (trace != null) {
						trace.writeBytes("NEWROOT " + newRootPageId+ lineSep);
						trace.flush();
					}
					newRoot.insertKey(rootEntry.key,
							((IndexData) rootEntry.data).getData());
					// the old root split and is now the left child of the new
					// root
					newRoot.setPrevPage(headerPage.getRoot());
					unpinPage(newRoot.getCurPage());
					try {
						updateHeader(newRootPageId);
					} catch (PinPageException e1) {
						// TODO Auto-generated catch block
						e1.printStackTrace();
					}
					
				} catch (ConstructPageException e) {
					// TODO Auto-generated catch block
					e.printStackTrace();
				} catch (IOException e) {
					// TODO Auto-generated catch block
					e.printStackTrace();
				} catch (IndexInsertRecException e) {
					// TODO Auto-generated catch block
					e.printStackTrace();
				} catch (UnpinPageException e) {
					// TODO Auto-generated catch block
					e.printStackTrace();
				}

			}
		
		// lazm a7tfz b el root elly kol mara hbd2 mno

		// hst5dm el method bta3t getPageNoByKey

		// ageeb el page elly btshawer 3leeha el key da
		// a pin el page elly gbtha
		// lw el page elly gt kant index page yb2a ana lesa mwsltesh
		// a3ml nfs elly 3mlto tany l7d ma awsel l leaf page
		// insert el data fy el leaf
		// lw 7sl overflow h split
		// lazm arg3 tany up w at2kd lw m7taga a3ml split tany l indexPage
		// lw el root 7slo split hwa kman m7taga a7ot root gdeed w a5ly en hwa
		// da el root
		if (trace != null) {
}
//		KeyDataEntry newRootEntry = null;
//
//		if (BT.getKeyLength(data) > headerPage.getKeySize())
//			throw new KeyTooLongException(null, "");
//
//		if (data instanceof StringKey) {
//			if (headerPage.getKeyType() != AttrType.attrString) {
//				throw new KeyNotMatchException(null, "");
//			}
//		} else if (data instanceof IntegerKey) {
//			if (headerPage.getKeyType() != AttrType.attrInteger) {
//				throw new KeyNotMatchException(null, "");
//			}
//		} else
//			throw new KeyNotMatchException(null, "");
//
//		// TWO CASES:
//		// 1. headerPage.root == INVALID_PAGE:
//		// - the tree is empty and we have to create a new first page;
//		// this page will be a leaf page
//		// 2. headerPage.root != INVALID_PAGE:
//		// - we call _insert() to insert the pair (key, rid)
//
////		if (trace != null) {
////			trace.writeBytes("INSERT " + rid.pageNo + " " + rid.slotNo + " "
////					+ data + lineSep);
////			trace.writeBytes("DO" + lineSep);
////			trace.flush();
////		}
//
//		if (headerPage.getRoot().pid == INVALID_PAGE) {
//			PageId newRootPageId;
//			BTLeafPage newRootPage = null;
//			RID dummyrid;
//
//			try {
//				newRootPage = new BTLeafPage(headerPage.getKeyType());
//			} catch (ConstructPageException e2) {
//				// TODO Auto-generated catch block
//				e2.printStackTrace();
//			}
//			newRootPageId = newRootPage.getCurPage();
//
//			if (trace != null) {
//				trace.writeBytes("NEWROOT " + newRootPageId + lineSep);
//				trace.flush();
//			}
//
//			newRootPage.setNextPage(new PageId(INVALID_PAGE));
//			newRootPage.setPrevPage(new PageId(INVALID_PAGE));
//
//			// ASSERTIONS:
//			// - newRootPage, newRootPageId valid and pinned
//
//			try {
//				newRootPage.insertRecord(data, rid);
//			} catch (LeafInsertRecException e1) {
//				// TODO Auto-generated catch block
//				e1.printStackTrace();
//			}
//
//			if (trace != null) {
//				trace.writeBytes("PUTIN node " + newRootPageId + lineSep);
//				trace.flush();
//			}
//
//			try {
//				unpinPage(newRootPageId, true);
//			} catch (UnpinPageException e) {
//				// TODO Auto-generated catch block
//				e.printStackTrace();
//			} /* = DIRTY */
//			try {
//				updateHeader(newRootPageId);
//			} catch (PinPageException e) {
//				// TODO Auto-generated catch block
//				e.printStackTrace();
//			} catch (UnpinPageException e) {
//				// TODO Auto-generated catch block
//				e.printStackTrace();
//			}
//
//			if (trace != null) {
//				trace.writeBytes("DONE" + lineSep);
//				trace.flush();
//			}
//
//			return;
//		}
//
//		// ASSERTIONS:
//		// - headerPageId, headerPage valid and pinned
//		// - headerPage.root holds the pageId of the root of the B-tree
//		// - none of the pages of the tree is pinned yet
//
//		if (trace != null) {
//			trace.writeBytes("SEARCH" + lineSep);
//			trace.flush();
//		}
//
//		try {
//			newRootEntry = insertP( headerPage.getRoot(),data, rid);
//		} catch (IteratorException e2) {
//			// TODO Auto-generated catch block
//			e2.printStackTrace();
//		} catch (DeleteRecException e2) {
//			// TODO Auto-generated catch block
//			e2.printStackTrace();
//		} catch (ConvertException e2) {
//			// TODO Auto-generated catch block
//			e2.printStackTrace();
//		} catch (NodeNotMatchException e2) {
//			// TODO Auto-generated catch block
//			e2.printStackTrace();
//		} catch (LeafInsertRecException e2) {
//			// TODO Auto-generated catch block
//			e2.printStackTrace();
//		} catch (UnpinPageException e2) {
//			// TODO Auto-generated catch block
//			e2.printStackTrace();
//		}
//
//		// TWO CASES:
//		// - newRootEntry != null: a leaf split propagated up to the root
//		// and the root split: the new pageNo is in
//		// newChildEntry.data.pageNo
//		// - newRootEntry == null: no new root was created;
//		// information on headerpage is still valid
//
//		// ASSERTIONS:
//		// - no page pinned
//
//		if (newRootEntry != null) {
//			BTIndexPage newRootPage = null;
//			PageId newRootPageId;
//
//			// the information about the pair <key, PageId> is
//			// packed in newRootEntry: extract it
//
//			try {
//				newRootPage = new BTIndexPage(headerPage.getKeyType());
//			} catch (ConstructPageException e1) {
//				// TODO Auto-generated catch block
//				e1.printStackTrace();
//			}
//			newRootPageId = newRootPage.getCurPage();
//
//			// ASSERTIONS:
//			// - newRootPage, newRootPageId valid and pinned
//			// - newEntryKey, newEntryPage contain the data for the new entry
//			// which was given up from the level down in the recursion
//
//			if (trace != null) {
//				trace.writeBytes("NEWROOT " + newRootPageId + lineSep);
//				trace.flush();
//			}
//
//			try {
//				newRootPage.insertKey(newRootEntry.key,
//						((IndexData) newRootEntry.data).getData());
//			} catch (IndexInsertRecException e) {
//				// TODO Auto-generated catch block
//				e.printStackTrace();
//			}
//
//			// the old root split and is now the left child of the new root
//			newRootPage.setPrevPage(headerPage.getRoot());
//
//			try {
//				unpinPage(newRootPageId, true /* = DIRTY */);
//			} catch (UnpinPageException e) {
//				// TODO Auto-generated catch block
//				e.printStackTrace();
//			}
//
//			try {
//				updateHeader(newRootPageId);
//			} catch (PinPageException e) {
//				// TODO Auto-generated catch block
//				e.printStackTrace();
//			} catch (UnpinPageException e) {
//				// TODO Auto-generated catch block
//				e.printStackTrace();
//			}
//
//		}
//
//		if (trace != null) {
//			trace.writeBytes("DONE" + lineSep);
//			trace.flush();
//		}
//
//		return;
	}

	private KeyDataEntry insertP(PageId currentPageId, KeyClass data, RID rid)
			throws IteratorException, DeleteRecException, ConvertException, NodeNotMatchException, LeafInsertRecException, UnpinPageException, IOException, ConstructPageException {
		BTSortedPage current;
		KeyDataEntry entry;
		Page page = new Page();
		try {
			page = pinPage(currentPageId);
		} catch (PinPageException e1) {
			// TODO Auto-generated catch block
			e1.printStackTrace();
		}
		short pageType;
		try {
			current = new BTSortedPage(page, headerPage.getKeyType());
			if (trace != null) {
				trace.writeBytes("VISIT node " + currentPageId + lineSep);
				trace.flush();
			}
			pageType = current.getType();
			if (pageType == NodeType.INDEX) {
				BTIndexPage currentIndex = new BTIndexPage(page,headerPage.getKeyType()) ;
				PageId currentIndexPageId = currentPageId;
				PageId nextId = null;
				try {
					nextId = currentIndex.getPageNoByKey(data);
				} catch (IndexSearchException e) {
					// TODO Auto-generated catch block
					e.printStackTrace();
				}
				// BTSortedPage nextPage = new BTSortedPage(nextId,
				// headerPage.getKeyType());
				unpinPage(currentPageId);
				entry = insertP(nextId, data, rid);
				if (entry == null) {
					// no split occurs
					return null;
				}
				currentIndex = new BTIndexPage(currentIndexPageId,
						headerPage.getKeyType());
				
				if (currentIndex.available_space() >= BT.getKeyDataLength(data,
						NodeType.INDEX)) {
					currentIndex.insertKey(entry.key,
							((IndexData) entry.data).getData());
					unpinPage(currentIndexPageId);
					return null;
					// we are done
				} else {
					// split
					entry = currentIndex.split(entry,currentIndexPageId,headerPage);
					// unpinPage(currentPageId);
					return entry;
				}

			} else {
				// leaf
				BTLeafPage leaf = new BTLeafPage(page,headerPage.getKeyType()) ;
				PageId currentLeafPageId = currentPageId;
				if (leaf.available_space() >= BT.getKeyDataLength(data,
						NodeType.LEAF)) {
					// no split
					leaf.insertRecord(data, rid);
					unpinPage(currentPageId);
					if (trace != null) {
						trace.writeBytes("PUTIN node " + currentLeafPageId
								+ lineSep);
						trace.flush();
					}
					return null;// indicates no split
					// we are done
				} else {
					// split
					KeyDataEntry currentEntry = leaf.split(data, rid,
							currentLeafPageId,headerPage);
					KeyDataEntry parentEntry = new KeyDataEntry(
							currentEntry.key, leaf.getNextPage());
					return parentEntry;
				}
			}
		} catch (ConstructPageException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		} catch (IOException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		} catch (NodeNotMatchException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		} catch (LeafInsertRecException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		} catch (UnpinPageException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		} catch (IndexInsertRecException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		} catch (btree.KeyNotMatchException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
		return null;
// ---------------------------------------------------------		
		
//		BTSortedPage currentPage;
//		Page page = null;
//		KeyDataEntry upEntry;
//
//		try {
//			page = pinPage(currentPageId);
//		} catch (PinPageException e) {
//			// TODO Auto-generated catch block
//			e.printStackTrace();
//		}
//		currentPage = new BTSortedPage(page, headerPage.getKeyType());
//
//		if (trace != null) {
//			trace.writeBytes("VISIT node " + currentPageId + lineSep);
//			trace.flush();
//		}
//
//		// TWO CASES:
//		// - pageType == INDEX:
//		// recurse and then split if necessary
//		// - pageType == LEAF:
//		// try to insert pair (key, rid), maybe split
//
//		if (currentPage.getType() == NodeType.INDEX) {
//			BTIndexPage currentIndexPage = new BTIndexPage(page,
//					headerPage.getKeyType());
//			PageId currentIndexPageId = currentPageId;
//			PageId nextPageId;
//
//			nextPageId = currentIndexPage.getPageNoByKey(data);
//
//			// now unpin the page, recurse and then pin it again
//			unpinPage(currentIndexPageId);
//
//			upEntry = insertP(nextPageId, data, rid);
//
//			// two cases:
//			// - upEntry == null: one level lower no split has occurred:
//			// we are done.
//			// - upEntry != null: one of the children has split and
//			// upEntry is the new data entry which has
//			// to be inserted on this index page
//
//			if (upEntry == null)
//				return null;
//
//			try {
//				currentIndexPage = new BTIndexPage(pinPage(currentPageId),
//						headerPage.getKeyType());
//			} catch (PinPageException e1) {
//				// TODO Auto-generated catch block
//				e1.printStackTrace();
//			}
//
//			// ASSERTIONS:
//			// - upEntry != null
//			// - currentIndexPage, currentIndexPageId valid and pinned
//
//			// the information about the pair <key, PageId> is
//			// packed in upEntry
//
//			// check whether there can still be entries inserted on that page
//			try {
//				if (currentIndexPage.available_space() >= BT.getKeyDataLength(
//						upEntry.key, NodeType.INDEX)) {
//
//					// no split has occurred
//					currentIndexPage.insertKey(upEntry.key,
//							((IndexData) upEntry.data).getData());
//
//					unpinPage(currentIndexPageId, true /* DIRTY */);
//
//					return null;
//				}
//			} catch (btree.KeyNotMatchException e) {
//				// TODO Auto-generated catch block
//				e.printStackTrace();
//			} catch (IndexInsertRecException e) {
//				// TODO Auto-generated catch block
//				e.printStackTrace();
//			}
//
//			// ASSERTIONS:
//			// - on the current index page is not enough space available .
//			// it splits
//
//			// therefore we have to allocate a new index page and we will
//			// distribute the entries
//			// - currentIndexPage, currentIndexPageId valid and pinned
//
//			BTIndexPage newIndexPage = null;
//			PageId newIndexPageId;
//
//			// we have to allocate a new INDEX page and
//			// to redistribute the index entries
//			try {
//				newIndexPage = new BTIndexPage(headerPage.getKeyType());
//			} catch (ConstructPageException e) {
//				// TODO Auto-generated catch block
//				e.printStackTrace();
//			}
//			newIndexPageId = newIndexPage.getCurPage();
//
//			if (trace != null) {
//				if (headerPage.getRoot().pid != currentIndexPageId.pid)
//					trace.writeBytes("SPLIT node " + currentIndexPageId
//							+ " IN nodes " + currentIndexPageId + " "
//							+ newIndexPageId + lineSep);
//				else
//					trace.writeBytes("ROOTSPLIT IN nodes " + currentIndexPageId
//							+ " " + newIndexPageId + lineSep);
//				trace.flush();
//			}
//
//			// ASSERTIONS:
//			// - newIndexPage, newIndexPageId valid and pinned
//			// - currentIndexPage, currentIndexPageId valid and pinned
//			// - upEntry containing (Key, Page) for the new entry which was
//			// given up from the level down in the recursion
//
//			KeyDataEntry tmpEntry;
//			RID delRid = new RID();
//
//			for (tmpEntry = currentIndexPage.getFirst(delRid); tmpEntry != null; tmpEntry = currentIndexPage
//					.getFirst(delRid)) {
//				try {
//					newIndexPage.insertKey(tmpEntry.key,
//							((IndexData) tmpEntry.data).getData());
//				} catch (IndexInsertRecException e) {
//					// TODO Auto-generated catch block
//					e.printStackTrace();
//				}
//				currentIndexPage.deleteSortedRecord(delRid);
//			}
//
//			// ASSERTIONS:
//			// - currentIndexPage empty
//			// - newIndexPage holds all former records from currentIndexPage
//
//			// we will try to make an equal split
//			RID firstRid = new RID();
//			KeyDataEntry undoEntry = null;
//			for (tmpEntry = newIndexPage.getFirst(firstRid); (currentIndexPage
//					.available_space() > newIndexPage.available_space()); tmpEntry = newIndexPage
//					.getFirst(firstRid)) {
//				// now insert the <key,pageId> pair on the new
//				// index page
//				undoEntry = tmpEntry;
//				try {
//					currentIndexPage.insertKey(tmpEntry.key,
//							((IndexData) tmpEntry.data).getData());
//				} catch (IndexInsertRecException e) {
//					// TODO Auto-generated catch block
//					e.printStackTrace();
//				}
//				newIndexPage.deleteSortedRecord(firstRid);
//			}
//
//			// undo the final record
//			if (currentIndexPage.available_space() < newIndexPage
//					.available_space()) {
//
//				try {
//					newIndexPage.insertKey(undoEntry.key,
//							((IndexData) undoEntry.data).getData());
//				} catch (IndexInsertRecException e) {
//					// TODO Auto-generated catch block
//					e.printStackTrace();
//				}
//
//				currentIndexPage
//						.deleteSortedRecord(new RID(currentIndexPage
//								.getCurPage(), (int) currentIndexPage
//								.getSlotCnt() - 1));
//			}
//
//			// check whether <newKey, newIndexPageId>
//			// will be inserted
//			// on the newly allocated or on the old index page
//
//			tmpEntry = newIndexPage.getFirst(firstRid);
//
//			try {
//				if (BT.keyCompare(upEntry.key, tmpEntry.key) >= 0) {
//					// the new data entry belongs on the new index page
//					newIndexPage.insertKey(upEntry.key,
//							((IndexData) upEntry.data).getData());
//				} else {
//					currentIndexPage.insertKey(upEntry.key,
//							((IndexData) upEntry.data).getData());
//
//					int i = (int) currentIndexPage.getSlotCnt() - 1;
//					tmpEntry = BT.getEntryFromBytes(currentIndexPage.getpage(),
//							currentIndexPage.getSlotOffset(i),
//							currentIndexPage.getSlotLength(i),
//							headerPage.getKeyType(), NodeType.INDEX);
//
//					newIndexPage.insertKey(tmpEntry.key,
//							((IndexData) tmpEntry.data).getData());
//
//					currentIndexPage.deleteSortedRecord(new RID(currentIndexPage
//							.getCurPage(), i));
//
//				}
//			} catch (btree.KeyNotMatchException e) {
//				// TODO Auto-generated catch block
//				e.printStackTrace();
//			} catch (IndexInsertRecException e) {
//				// TODO Auto-generated catch block
//				e.printStackTrace();
//			}
//
//			unpinPage(currentIndexPageId, true /* dirty */);
//
//			// fill upEntry
//			upEntry = newIndexPage.getFirst(delRid);
//
//			// now set prevPageId of the newIndexPage to the pageId
//			// of the deleted entry:
//			newIndexPage.setPrevPage(((IndexData) upEntry.data).getData());
//
//			// delete first record on new index page since it is given up
//			newIndexPage.deleteSortedRecord(delRid);
//
//			unpinPage(newIndexPageId, true /* dirty */);
//
////			if (trace != null) {
////				trace_children(currentIndexPageId);
////				trace_children(newIndexPageId);
////			}
//
//			((IndexData) upEntry.data).setData(newIndexPageId);
//
//			return upEntry;
//
//			// ASSERTIONS:
//			// - no pages pinned
//			// - upEntry holds the pointer to the KeyDataEntry which is
//			// to be inserted on the index page one level up
//
//		}
//
//		else if (currentPage.getType() == NodeType.LEAF) {
//			BTLeafPage currentLeafPage = new BTLeafPage(page,
//					headerPage.getKeyType());
//
//			PageId currentLeafPageId = currentPageId;
//
//			// ASSERTIONS:
//			// - currentLeafPage, currentLeafPageId valid and pinned
//
//			// check whether there can still be entries inserted on that page
//			try {
//				if (currentLeafPage.available_space() >= BT.getKeyDataLength(data,
//						NodeType.LEAF)) {
//					// no split has occurred
//
//					currentLeafPage.insertRecord(data, rid);
//
//					unpinPage(currentLeafPageId, true /* DIRTY */);
//
//					if (trace != null) {
//						trace.writeBytes("PUTIN node " + currentLeafPageId
//								+ lineSep);
//						trace.flush();
//					}
//
//					return null;
//				}
//			} catch (btree.KeyNotMatchException e1) {
//				// TODO Auto-generated catch block
//				e1.printStackTrace();
//			}
//
//			// ASSERTIONS:
//			// - on the current leaf page is not enough space available.
//			// It splits.
//			// - therefore we have to allocate a new leaf page and we will
//			// - distribute the entries
//
//			BTLeafPage newLeafPage = null;
//			PageId newLeafPageId;
//			// we have to allocate a new LEAF page and
//			// to redistribute the data entries entries
//			try {
//				newLeafPage = new BTLeafPage(headerPage.getKeyType());
//			} catch (ConstructPageException e) {
//				// TODO Auto-generated catch block
//				e.printStackTrace();
//			}
//			newLeafPageId = newLeafPage.getCurPage();
//
//			newLeafPage.setNextPage(currentLeafPage.getNextPage());
//			newLeafPage.setPrevPage(currentLeafPageId); // for dbl-linked list
//			currentLeafPage.setNextPage(newLeafPageId);
//
//			// change the prevPage pointer on the next page:
//
//			PageId rightPageId;
//			rightPageId = newLeafPage.getNextPage();
//			if (rightPageId.pid != INVALID_PAGE) {
//				BTLeafPage rightPage = null;
//				try {
//					rightPage = new BTLeafPage(rightPageId,
//							headerPage.getKeyType());
//				} catch (ConstructPageException e) {
//					// TODO Auto-generated catch block
//					e.printStackTrace();
//				}
//
//				rightPage.setPrevPage(newLeafPageId);
//				unpinPage(rightPageId, true /* = DIRTY */);
//
//				// ASSERTIONS:
//				// - newLeafPage, newLeafPageId valid and pinned
//				// - currentLeafPage, currentLeafPageId valid and pinned
//			}
//
//			if (trace != null) {
//				if (headerPage.getRoot().pid != currentLeafPageId.pid)
//					trace.writeBytes("SPLIT node " + currentLeafPageId
//							+ " IN nodes " + currentLeafPageId + " "
//							+ newLeafPageId + lineSep);
//				else
//					trace.writeBytes("ROOTSPLIT IN nodes " + currentLeafPageId
//							+ " " + newLeafPageId + lineSep);
//				trace.flush();
//			}
//
//			KeyDataEntry tmpEntry;
//			RID firstRid = new RID();
//
//			for (tmpEntry = currentLeafPage.getFirst(firstRid); tmpEntry != null; tmpEntry = currentLeafPage
//					.getFirst(firstRid)) {
//
//				newLeafPage.insertRecord(tmpEntry.key,
//						((LeafData) (tmpEntry.data)).getData());
//				currentLeafPage.deleteSortedRecord(firstRid);
//
//			}
//
//			// ASSERTIONS:
//			// - currentLeafPage empty
//			// - newLeafPage holds all former records from currentLeafPage
//
//			KeyDataEntry undoEntry = null;
//			for (tmpEntry = newLeafPage.getFirst(firstRid); newLeafPage
//					.available_space() < currentLeafPage.available_space(); tmpEntry = newLeafPage
//					.getFirst(firstRid)) {
//				undoEntry = tmpEntry;
//				currentLeafPage.insertRecord(tmpEntry.key,
//						((LeafData) tmpEntry.data).getData());
//				newLeafPage.deleteSortedRecord(firstRid);
//			}
//
//			try {
//				if (BT.keyCompare(data, undoEntry.key) < 0) {
//					// undo the final record
//					if (currentLeafPage.available_space() < newLeafPage
//							.available_space()) {
//						newLeafPage.insertRecord(undoEntry.key,
//								((LeafData) undoEntry.data).getData());
//
//						currentLeafPage.deleteSortedRecord(new RID(currentLeafPage
//								.getCurPage(),
//								(int) currentLeafPage.getSlotCnt() - 1));
//					}
//				}
//			} catch (btree.KeyNotMatchException e1) {
//				// TODO Auto-generated catch block
//				e1.printStackTrace();
//			}
//
//			// check whether <key, rid>
//			// will be inserted
//			// on the newly allocated or on the old leaf page
//
//			try {
//				if (BT.keyCompare(data, undoEntry.key) >= 0) {
//					// the new data entry belongs on the new Leaf page
//					newLeafPage.insertRecord(data, rid);
//
//					if (trace != null) {
//						trace.writeBytes("PUTIN node " + newLeafPageId + lineSep);
//						trace.flush();
//					}
//
//				} else {
//					currentLeafPage.insertRecord(data, rid);
//				}
//			} catch (btree.KeyNotMatchException e) {
//				// TODO Auto-generated catch block
//				e.printStackTrace();
//			}
//
//			unpinPage(currentLeafPageId, true /* dirty */);
//
////			if (trace != null) {
////				trace_children(currentLeafPageId);
////				trace_children(newLeafPageId);
////			}
//
//			// fill upEntry
//			tmpEntry = newLeafPage.getFirst(firstRid);
//			upEntry = new KeyDataEntry(tmpEntry.key, newLeafPageId);
//
//			unpinPage(newLeafPageId, true /* dirty */);
//
//			// ASSERTIONS:
//			// - no pages pinned
//			// - upEntry holds the valid KeyDataEntry which is to be inserted
//			// on the index page one level up
//			return upEntry;
//		}
//		return null; 

	}

	// private void insertP(PageId pidParent, PageId pidChild, KeyClass data,
	// RID rid) {
	// boolean cantInsert = false;
	// try {
	//
	// BTSortedPage next = new BTSortedPage(pidChild,
	// headerPage.getKeyType());
	//
	// if (next.getType() == NodeType.INDEX) {
	//
	// BTIndexPage newParent = (BTIndexPage) next;
	// PageId newChildId = newParent.getPageNoByKey(data);
	// KeyDataEntry newEntry = new KeyDataEntry(data, rid);
	// if (newParent.available_space() < BT.getKeyDataLength(data,
	// newParent.getType())) {
	//
	// //newParent.split();
	// BTIndexPage oldParent = new
	// BTIndexPage(pidParent,headerPage.getKeyType());
	// PageId nextChildId = newParent.getNextPage();
	// BTIndexPage nextChild = new
	// BTIndexPage(nextChildId,headerPage.getKeyType());
	// RID newRid= new RID(nextChildId,0);
	// KeyDataEntry firstEntry = nextChild.getFirst(newRid);
	// KeyDataEntry newEntryP = new KeyDataEntry(firstEntry.key, nextChildId);
	// insertP(pidParent, nextChildId, data, newRid);
	// }
	// newParent.insertRecord(newEntry);
	// // BTSortedPage newChild = new BTSortedPage(newChildId,
	// // headerPage.getKeyType());
	// insertP(pidChild, newChildId, data, rid);
	// }
	// } catch (ConstructPageException e) {
	// // TODO Auto-generated catch block
	// e.printStackTrace();
	// } catch (IOException e) {
	// // TODO Auto-generated catch block
	// e.printStackTrace();
	// } catch (InsertRecException e) {
	// // TODO Auto-generated catch block
	// cantInsert = true;
	// e.printStackTrace();
	// } catch (KeyNotMatchException e) {
	// // TODO Auto-generated catch block
	// e.printStackTrace();
	// } catch (NodeNotMatchException e) {
	// // TODO Auto-generated catch block
	// e.printStackTrace();
	// } catch (IteratorException e) {
	// // TODO Auto-generated catch block
	// e.printStackTrace();
	// }
	//
	//
	// }
	//
	// private void insertP(PageId pidParent,PageId pidChild,KeyClass data,RID
	// rid)
	// {
	// try {
	// BTSortedPage next = new BTSortedPage(pidChild,headerPage.getKeyType());
	//
	// if(next.getType()==NodeType.INDEX){
	// BTIndexPage newParent = (BTIndexPage) next;
	// PageId newChildId = newParent.getPageNoByKey(data);
	// KeyDataEntry newEntry = new KeyDataEntry(data, rid);
	// newParent.insertRecord(newEntry);
	// //BTSortedPage newChild = new BTSortedPage(newChildId,
	// headerPage.getKeyType());
	// insertP(pidChild, newChildId, data,rid);
	//
	// }
	// } catch (ConstructPageException e) {
	// // TODO Auto-generated catch block
	// e.printStackTrace();
	// } catch (IOException e) {
	// // TODO Auto-generated catch block
	// e.printStackTrace();
	// } catch (InsertRecException e) {
	// // TODO Auto-generated catch block
	//
	// e.printStackTrace();
	// }
	// }

	public void close() {
		if (headerPage != null) {
			try {
				unpinPage(headerPage.getRoot(), true);
			} catch (UnpinPageException e) {
				// TODO Auto-generated catch block
				//e.printStackTrace();
			}
		}
		headerPage = null;
	}

	// done
	private void destroy(PageId currentPageId) {
		try {
			Page page = pinPage(currentPageId);
			BTSortedPage current = new BTSortedPage(page,
					headerPage.getKeyType());
			if (current.getType() == NodeType.INDEX) {
				RID recored = new RID();
				BTIndexPage currentIndexPage = null;
				try {
					currentIndexPage = new BTIndexPage(page,
							headerPage.getKeyType());
				} catch (ConstructPageException e) {
					// TODO Auto-generated catch block
					e.printStackTrace();
				}
				PageId childId;
				KeyDataEntry currentEntry = currentIndexPage.getFirst(recored);
				for (KeyDataEntry entry = currentEntry; entry != null; currentIndexPage
						.getNext(recored)) {
					 childId = ((IndexData) (entry.data)).getData();
					destroy(childId);
				}
				
			} else {
				unpinPage(currentPageId);
				freePage(currentPageId);
			}
		} catch (IOException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		} catch (PinPageException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		} catch (IteratorException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		} catch (UnpinPageException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		} catch (FreePageException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
	}

	// done
	public void destroyFile() {
		if (headerPage != null) {
			PageId pgId = headerPage.getRoot();
			//BTSortedPage current;
			if (pgId.pid != INVALID_PAGE) {
				destroy(pgId);
			}

			try {
				unpinPage(headerPage.getRoot());
				freePage(headerPage.getRoot());
				delete_file_entry(headerPage.getFileName());
				headerPage = null;
			} catch (UnpinPageException e) {
				// TODO Auto-generated catch block
				e.printStackTrace();
			} catch (FreePageException e) {
				// TODO Auto-generated catch block
				e.printStackTrace();
			} catch (DeleteFileEntryException e) {
				// TODO Auto-generated catch block
				e.printStackTrace();
			}

		}
	}

	// done
	public BTFileScan new_scan(KeyClass lo_key, KeyClass hi_key)
			throws UnpinPageException, PinPageException, IteratorException,
			KeyNotMatchException, IOException, btree.KeyNotMatchException {
		BTFileScan scan = new BTFileScan();
		// BTree is empty
		if (headerPage.getRoot().pid == INVALID_PAGE) {
			scan.leafPage = null;
			return scan;
		}
		//
		scan.setEndkey(hi_key);
		scan.setScanFirst(false);
		scan.setCurrentDeleted(false);
		scan.setCurRid(new RID());
		scan.setKeyType(headerPage.getKeyType());
		scan.setMaxKeysize(headerPage.getKeySize());
		scan.setBtree(this);

		// this sets up scan at the starting position, ready for iteration
		scan.leafPage = getFirstLeafPage(lo_key, scan.getCurRid());
		return scan;
	}

	

	BTLeafPage getFirstLeafPage(KeyClass lowKey, RID startrid)
			throws UnpinPageException, PinPageException, IteratorException,
			KeyNotMatchException, IOException, btree.KeyNotMatchException {

//		PageId pageNo = headerPage.getRoot();
//		BTIndexPage indexPage = null;
//		KeyDataEntry entry;
//		PageId prevpageno;
//		Page page = null;
//		PageId nextpageno;
//		// ------if root empty
//		if (pageNo.pid == INVALID_PAGE) { // no pages in the BTREE
//			return null;
//		}
//
//		// ------if root page is valid
//		page = pinPage(pageNo);
//
//		// -----put in sorted page
//		BTSortedPage tempSorted = new BTSortedPage(page,
//				headerPage.getKeyType());
//		if (trace != null) {
//			trace.writeBytes("VISIT node " + pageNo + lineSep);
//			trace.flush();
//		}
//		// ----if tempSorted is index
//		
//		while (tempSorted.getType() == NodeType.INDEX) {
//			// index page
//			try {
//				indexPage = new BTIndexPage(page, headerPage.getKeyType());
//			} catch (ConstructPageException e) {
//				// TODO Auto-generated catch block
//				e.printStackTrace();
//			}
//			// previous page
//			prevpageno = indexPage.getPrevPage();
//			// first entry in index page
//			entry = indexPage.getFirst(startrid);
//			// get correct indexPage
//			while (entry != null && lowKey != null
//					&& BT.keyCompare(entry.key, lowKey) < 0) {
//
//				prevpageno = ((IndexData) entry.data).getData();
//				entry = indexPage.getNext(startrid);
//			}
//			// unpin page that i pinned it
//			unpinPage(pageNo);
//
//			pageNo = prevpageno;
//			// page of the leafPage
//			 page = pinPage(pageNo);
//			
//			if (trace != null) {
//				trace.writeBytes("VISIT node " + pageNo + lineSep);
//				trace.flush();
//			}
//		}
//			// ------------------------get proper leaf Page---------------------
//			BTLeafPage pageLeaf = new BTLeafPage(page, headerPage.getKeyType());
//
//			entry = pageLeaf.getFirst(startrid);
//
//			// -------------if we have empty pages in first------------
//			while (entry == null) {
//				// get next
//				nextpageno = pageLeaf.getNextPage();
//				// upin page that i pinned it
//				unpinPage(pageNo);
//				if (nextpageno.pid == INVALID_PAGE) {
//					// all records are empty
//					return null;
//				}
//
//				pageNo = nextpageno;
//				// get next page
//				pageLeaf = new BTLeafPage(pinPage(pageNo),
//						headerPage.getKeyType());
//				// get first entry in the page
//				entry = pageLeaf.getFirst(startrid);
//			}
//			// ----------------here i get leaf Page---------------------
//			// -------------here check the key of the leaf page----------
//
//			if (lowKey == null) {
//				// return leaf page i get
//				// still pinned "note!"
//				return pageLeaf;
//			}
//			// get proper leaf page with low key
//			while (BT.keyCompare(entry.key, lowKey) < 0) {
//				// -----------------entry has key less than low key
//				// given---------------
//				// next entry
//				entry = pageLeaf.getNext(startrid);
//				while (entry == null) {
//					// loop over leaf pages
//					nextpageno = pageLeaf.getNextPage();
//					unpinPage(pageNo);
//
//					if (nextpageno.pid == INVALID_PAGE) {
//						return null;
//					}
//
//					pageNo = nextpageno;
//					pageLeaf = new BTLeafPage(pinPage(pageNo),
//							headerPage.getKeyType());
//					entry = pageLeaf.getFirst(startrid);
//				}
//				// page is already pinned
//			}
//
//			return pageLeaf;
		
		
		BTLeafPage pageLeaf;
		BTIndexPage pageIndex = null;
		Page page;
		BTSortedPage sortPage;
		PageId pageno;
		PageId curpageno = null; // iterator
		PageId prevpageno;
		PageId nextpageno;
		RID curRid;
		KeyDataEntry curEntry;

		pageno = headerPage.getRoot();

		if (pageno.pid == INVALID_PAGE) { // no pages in the BTREE
			pageLeaf = null; // should be handled by
			// startrid =INVALID_PAGEID ; // the caller
			return pageLeaf;
		}

		page = pinPage(pageno);
		sortPage = new BTSortedPage(page, headerPage.getKeyType());

		if (trace != null) {
			trace.writeBytes("VISIT node " + pageno + lineSep);
			trace.flush();
		}

		// ASSERTION
		// - pageno and sortPage is the root of the btree
		// - pageno and sortPage valid and pinned 

		while (sortPage.getType() == NodeType.INDEX) {
			
			//root elly hea index
			try {
				pageIndex = new BTIndexPage(page, headerPage.getKeyType());
			} catch (ConstructPageException e) {
				// TODO Auto-generated catch block
				e.printStackTrace();
			}
			//mesh fahma previous leeh 
			prevpageno = pageIndex.getPrevPage();
			//awel record 3andy
			curEntry = pageIndex.getFirst(startrid);
			
			
			while (curEntry != null && lowKey != null
					&& BT.keyCompare(curEntry.key, lowKey) < 0) {

				prevpageno = ((IndexData) curEntry.data).getData();
				curEntry = pageIndex.getNext(startrid);
			}

			unpinPage(pageno);

			pageno = prevpageno;
			page = pinPage(pageno);
			sortPage = new BTSortedPage(page, headerPage.getKeyType());

			if (trace != null) {
				trace.writeBytes("VISIT node " + pageno + lineSep);
				trace.flush();
			}

		}

		pageLeaf = new BTLeafPage(page, headerPage.getKeyType());

		curEntry = pageLeaf.getFirst(startrid);
		while (curEntry == null) {
			// skip empty leaf pages off to left
			nextpageno = pageLeaf.getNextPage();
			unpinPage(pageno);
			if (nextpageno.pid == INVALID_PAGE) {
				// oops, no more records, so set this scan to indicate this.
				return null;
			}

			pageno = nextpageno;
			pageLeaf = new BTLeafPage(pinPage(pageno), headerPage.getKeyType());
			curEntry = pageLeaf.getFirst(startrid);
		}

		// ASSERTIONS:
		// - curkey, curRid: contain the first record on the
		// current leaf page (curkey its key, cur
		// - pageLeaf, pageno valid and pinned

		if (lowKey == null) {
			return pageLeaf;
			// note that pageno/pageLeaf is still pinned;
			// scan will unpin it when done
		}

		while (BT.keyCompare(curEntry.key, lowKey) < 0) {
			curEntry = pageLeaf.getNext(startrid);
			while (curEntry == null) { // have to go right
				nextpageno = pageLeaf.getNextPage();
				unpinPage(pageno);

				if (nextpageno.pid == INVALID_PAGE) {
					return null;
				}

				pageno = nextpageno;
				pageLeaf = new BTLeafPage(pinPage(pageno),
						headerPage.getKeyType());

				curEntry = pageLeaf.getFirst(startrid);
			}
		}

		return pageLeaf;


	}
	// -------------------------------------------------------------------------------------
	public static Page pinPage(PageId pageno) throws PinPageException {
		try {
			Page page = new Page();
			SystemDefs.JavabaseBM.pinPage(pageno, page, false/* Rdisk */);
			return page;
		} catch (Exception e) {
			e.printStackTrace();
			throw new PinPageException(e, "");
		}
	}

	public static void unpinPage(PageId pageno) throws UnpinPageException {
		try {
			SystemDefs.JavabaseBM.unpinPage(pageno, true /* = not DIRTY */);
		} catch (Exception e) {
			e.printStackTrace();
			throw new UnpinPageException(e, "");
		}
	}

	private void freePage(PageId pageno) throws FreePageException {
		try {
			SystemDefs.JavabaseBM.freePage(pageno);
		} catch (Exception e) {
			e.printStackTrace();
			throw new FreePageException(e, "");
		}

	}

	private void delete_file_entry(String filename)
			throws DeleteFileEntryException {
		try {
			SystemDefs.JavabaseDB.delete_file_entry(filename);
		} catch (Exception e) {
			e.printStackTrace();
			throw new DeleteFileEntryException(e, "");
		}
	}

	private void unpinPage(PageId pageno, boolean dirty)
			throws UnpinPageException {
		try {
			SystemDefs.JavabaseBM.unpinPage(pageno, dirty);
		} catch (Exception e) {
			//e.printStackTrace();
		//	throw new UnpinPageException(e, "");
		}
	}
	private boolean NaiveDelete(KeyClass key, RID rid)
			throws LeafDeleteException, KeyNotMatchException, PinPageException,
			ConstructPageException, IOException, UnpinPageException,
			PinPageException, IndexSearchException, IteratorException, btree.KeyNotMatchException {
		BTLeafPage leafPage;
		RID curRid = new RID(); // iterator
		PageId nextpage;
		KeyDataEntry entry;

		 if (trace != null) {
		 trace.writeBytes("DELETE " + rid.pageNo + " " + rid.slotNo + " "
		 + key + lineSep);
		 trace.writeBytes("DO" + lineSep);
		 trace.writeBytes("SEARCH" + lineSep);
		 trace.flush();
		 }

		leafPage = getFirstLeafPage(key, curRid); // find first page,rid of key
		if (leafPage == null)
			return false;

		entry = leafPage.getCurrent(curRid);

		while (true) {

			while (entry == null) { // have to go right
				nextpage = leafPage.getNextPage();
				unpinPage(leafPage.getCurPage());
				if (nextpage.pid == INVALID_PAGE) {
					return false;
				}

				leafPage = new BTLeafPage(pinPage(nextpage),
						headerPage.getKeyType());
				entry = leafPage.getFirst(new RID());
			}

			if (BT.keyCompare(key, entry.key) > 0)
				break;

			if (leafPage.delEntry(new KeyDataEntry(key, rid)) == true) {

				// successfully found <key, rid> on this page and deleted it.
				// unpin dirty page and return OK.
				unpinPage(leafPage.getCurPage(), true /* = DIRTY */);

				 if (trace != null) {
				 trace.writeBytes("TAKEFROM node " + leafPage.getCurPage()
				 + lineSep);
				 trace.writeBytes("DONE" + lineSep);
				 trace.flush();
				 }

				return true;
			}

			nextpage = leafPage.getNextPage();
			unpinPage(leafPage.getCurPage());

			leafPage = new BTLeafPage(pinPage(nextpage),
					headerPage.getKeyType());

			entry = leafPage.getFirst(curRid);
		}

		/*
		 * We reached a page with first key > `key', so return an error. We
		 * should have got true back from delUserRid above. Apparently the
		 * specified <key,rid> data entry does not exist.
		 */

		unpinPage(leafPage.getCurPage());
		return false;
	}

	void trace_children(PageId id) throws IOException, IteratorException,
	ConstructPageException, PinPageException, UnpinPageException {

if (trace != null) {

	BTSortedPage sortedPage;
	RID metaRid = new RID();
	KeyDataEntry entry;
	sortedPage = new BTSortedPage(pinPage(id), headerPage.getKeyType());

	// Now print all the child nodes of the page.
	if (sortedPage.getType() == NodeType.INDEX) {
		BTIndexPage indexPage = new BTIndexPage(sortedPage,
				headerPage.getKeyType());
		trace.writeBytes("INDEX CHILDREN " + id + " nodes" + lineSep);
		trace.writeBytes(" " + indexPage.getPrevPage());
		for (entry = indexPage.getFirst(metaRid); entry != null; entry = indexPage
				.getNext(metaRid)) {
			trace.writeBytes("   " + ((IndexData) entry.data).getData());
		}
	} else if (sortedPage.getType() == NodeType.LEAF) {
		BTLeafPage leafPage = new BTLeafPage(sortedPage,
				headerPage.getKeyType());
		trace.writeBytes("LEAF CHILDREN " + id + " nodes" + lineSep);
		for (entry = leafPage.getFirst(metaRid); entry != null; entry = leafPage
				.getNext(metaRid)) {
			trace.writeBytes("   " + entry.key + " " + entry.data);
		}
	}
	unpinPage(id);
	trace.writeBytes(lineSep);
	trace.flush();
}

}

}
